Module# 05: Linked List Lecture#19: Programming for Linked List Part-II
/* For the sake of
completion, use the declaration of JLinkedList<T> here first and then add
the methods for insertion, printing and merging. */
// Example 19.1: Declaring
a method to delete at FRONT
// Example 19.2: Declaring
a method to delete at END
// Example 19.3: Declaring
a method to delete at ANY
// Example 19.4: Linked
list with insertion, and deletion operations
// This program shows how
to define a (single) linked list
class JLinkedList<T> {
Node head; // head of list
class Node {
T data;
Node next;
// Constructor
Node (){
data = null;
next = null;
}
Node(T d){
data = d;
next = null;
}
}
JLinkedList(){ //LinkedList Header Node
head = new Node();
}
// Methods to maintain the
collection are defined below…
// Declaring a method to
insert at FRONT
public void insertFront(T data){
// Create a new node with
given data
Node newNode = new Node(data);
newNode.next = this.head.next;
// Make the new node as as
the first node
this.head.next = newNode;
}
// Declaring a method to
insert at END
public void insertEnd(T data){
Node newNode = new Node(data);
newNode.next = null;
Node temp = this.head;
while(temp.next != null) {
temp = temp.next;
}
temp.next = new_node;
}
// Declaring a method to
insert at ANY
public void insertKey(T data , T key) {
Node newNode = new Node(data);
newNode.next = null;
Node temp = this.head;
boolean status = false;
while(temp != null){
if(temp.data == key) {
status = true;
break;
}
temp = temp.next;
}
if(status) {
newNode.next = temp.next;
temp.next = newNode;
}
}
// Declaring a method to
print a list
public void printList(){
Node currNode = this.head.next;
System.out.print("LinkedList:
");
// Traverse through the
LinkedList
while(currNode != null) {
// Print the
data at current node
System.out.print(currNode.data + " ");
// Go to next
node
currNode = currNode.next;
}
System.out.println();
}
// Declaring a method to
merge two lists
public void merge(JLinkedList<T> l2) {
Node l1Node = this.head;
Node l2Node = l2.head;
while(l1Node.next != null ) {
l1Node = l1Node.next;
}
l1Node.next = l2Node.next;
free(l2.head); // Return the node to free
memory
}
// Example 19.1: Declaring
a method to delete at FRONT
public T deleteFront() {
T x = null;
Node temp = this.head, prev = null;
if(temp != null) {
x = temp.data;
this.head = temp.next; // Changed head
// Display the
message
System.out.println("Element
deleted");
}
return x; // Return the
deleted data
}
// Example 19.2: Declaring
a method to delete at END
public T deleteEnd () {
T x = null;
Node temp = this.head, prev = null;
if (temp != null) { // If the list is not empty
while(temp != null) { // Move to the end
node
prev = temp;
temp = temp.next;
}
x = prev.data;
prev.next = null;
}
return x;
}
// Example
19.3: Declaring a method to delete at ANY
public void deleteAny(int key){
Node temp = this.head, prev = null;
while(temp != null) {
if(temp.data == key) {
prev.next = temp.next;
// Display the message
System.out.println(key+ " position
element deleted");
break;
}
else {
prev = temp;
temp = temp.next;
}
}
}
} // End of
declaration of JLiknkedList<T>
// Example 19.4: Linked
list with insertion, and deletion operations
// The diver class is
defined below…
// Continued on ….
class LinkedListDeletionDemo {
public static void main(String[] args) {
JLinkedList<Integer> list = new JLinkedList<Integer>();
list.insertFront(1);
list.insertFront(2);
list.insertFront(3);
list.insertFront(4);
list.insertFront(5);
list.insertFront(6);
list.insertFront(7);
list.insertFront(8);
// Print the LinkedList
list.printList();
list.deleteKey(4);
list.printList();
list.deleteFront( );
list.printList();
list.deleteEnd();
list.printList();
}
} // End of the main program
/*
For the sake of completion,
use the declaration of JLinkedList<T> here first and then add the methods
for insertion, deletion, printing and merging.
Ultimately, this is the
wjhold program for the linked list collection.
*/
// Example 19.5: Defining a
method to reverse a list
// Example 19.6: Creation
of a list and reversal
// This program shows how
to define a (single) linked list
class JLinkedList<T> {
Node head; // head of list
class Node {
T data;
Node next;
// Constructor
Node (){
data = null;
next = null;
}
Node(T d){
data = d;
next = null;
}
}
JLinkedList(){ //LinkedList Header Node
head = new Node();
}
// Methods to maintain the
collection are defined below…
// Declaring a method to
insert at FRONT
public void insertFront(T data){
// Create a new node with
given data
Node newNode = new Node(data);
newNode.next = this.head.next;
// Make the new node as as
the first node
this.head.next = newNode;
}
// Declaring a method to
insert at END
public void insertEnd(T data){
Node newNode = new Node(data);
newNode.next = null;
Node temp = this.head;
while(temp.next != null) {
temp = temp.next;
}
temp.next = new_node;
}
// Declaring a method to
insert at ANY
public void insertKey(T data , T key) {
Node newNode = new Node(data);
newNode.next = null;
Node temp = this.head;
boolean status = false;
while(temp != null){
if(temp.data == key) {
status = true;
break;
}
temp = temp.next;
}
if(status) {
newNode.next = temp.next;
temp.next = newNode;
}
}
// Declaring a method to
print a list
public void printList(){
Node currNode = this.head.next;
System.out.print("LinkedList:
");
// Traverse through the
LinkedList
while(currNode != null) {
// Print the
data at current node
System.out.print(currNode.data + " ");
// Go to next
node
currNode = currNode.next;
}
System.out.println();
}
// Declaring a method to
merge two lists
public void merge(JLinkedList<T> l2) {
Node l1Node = this.head;
Node l2Node = l2.head;
while(l1Node.next != null ) {
l1Node = l1Node.next;
}
l1Node.next = l2Node.next;
free(l2.head); // Return the node to free
memory
}
// Declaring a method to
delete at FRONT
public T deleteFront() {
T x = null;
Node temp = this.head, prev = null;
if(temp != null) {
x = temp.data;
this.head = temp.next; // Changed head
// Display the
message
System.out.println("Element
deleted");
}
return x; // Return the
deleted data
}
// Declaring a method to
delete at END
public T deleteEnd () {
T x = null;
Node temp = this.head, prev = null;
if (temp != null) { // If the list is not empty
while(temp != null) { // Move to the end
node
prev = temp;
temp = temp.next;
}
x = prev.data;
prev.next = null;
}
return x;
}
// Declaring a method to
delete at ANY
public void deleteAny(int key){
Node temp
= this.head, prev = null;
while(temp != null) {
if(temp.data == key) {
prev.next = temp.next;
// Display the message
System.out.println(key+ " position
element deleted");
break;
}
else {
prev = temp;
temp = temp.next;
}
}
}
// Example 19.5: Defining a
method to reverse a list
public Node rev(Node n) {
Node current = n;
Node next = n.next;
Node prev = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head.next = prev;
return next;
}
public void reverse() {
Node currNode = this.head.next;
System.out.print("Reversed
List : ");
rev(currNode);
}
} // End of
declaration of JLiknkedList<T>
// The following is the
main program illustrating the linked list
// Example 19.6: Creation
of a list and reversal
// Continued on ….
class LinkeListReversalDemo{
public static void main(String args[]) {
JLinkedList<Integer> list = new JLinkedList<Integer>();
list.insertEnd(9);
list.printList();
list.insertFront(5);
list.printList();
list.insertEnd(10);
list.printList();
list.insertKey(7,5);
list.printList();
list.insertKey(12,0);
list.printList();
list.insertKey(13,10);
list.printList();
list.insertFront(2);
list.printList();
list.reverse();
list.printList();
}
}